package com.lw.leetcode.back.b;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 994. 腐烂的橘子
 *
 * @Author liw
 * @Date 2021/4/21 17:55
 * @Version 1.0
 */
public class OrangesRotting {


    public static void main(String[] args) {
        OrangesRotting test = new OrangesRotting();
//        int[][] arr = {{2, 1, 1}, {1, 1, 0}, {0, 1, 1}};
        int[][] arr = {{2, 1, 0}, {1, 0, 0}, {0, 0, 0}};
        int i = test.orangesRotting(arr);
        System.out.println(i);
    }


    private int[][] grid;
    private int a;
    private int b;
    private int count = 0;
    private int c = 0;
    private Queue<Integer> queue = new LinkedList<>();
    public int orangesRotting(int[][] grid) {
        a = grid.length;
        b = grid[0].length;
        this.grid = grid;
        for (int i = 0; i < a; i++) {
            for (int j = 0; j < b; j++) {
                if (grid[i][j] == 1) {
                    count++;
                }
                if (grid[i][j] == 2) {
                    queue.add((i << 4) + j);
                    grid[i][j] = -1;
                }
            }
        }
        queue.add(null);
        if (count == 0) {
            return c;
        }
        while (queue.size() > 1) {
            if (count == 0) {
                return c + 1;
            }
            Integer poll = queue.poll();
            if (poll == null) {
                queue.add(null);
                c++;
            } else {
                int x = poll >> 4;
                int y = poll & 0xf;

                find(x - 1, y);
                find(x + 1, y);
                find(x, y + 1);
                find(x, y - 1);
            }
        }
        return -1;
    }

    private void find(int x, int y) {
        if (x < 0 || x == a || y < 0 || y == b) {
            return;
        }
        if (grid[x][y] == 1) {
            queue.add((x << 4) + y);
            grid[x][y] = -1;
            count--;
        }
    }

}
